package sort.yht;

import sort.util.Constants;
import sort.util.MySort;

/**
 * 功能描述：基数排序
 *
 * @Author: yht
 * @Date: 2021/8/11 14:15
 */
public class JiShu2 implements MySort {

  class Progress{
    int now;

    Progress(int now) {
      this.now = now;
    }
  }

  @Override
  public String getName() {
    return "【基数排序】";
  }

  @Override
  public int[] sort(int[] a) {
//    doSort(a, a, a.length, Constants.MAX_DATA_VALUE, new Progress(0));
    doSort2(a);
    return a;
  }

  /**
   * 基数排序，这种方法是从高位到地位，递归装桶，
   * 最后按顺序从桶中把数据拿出来放回去，配合快速排序，总体效率和快速排序相当
   * 这种方法空间复杂度很高，效率也不算很快，鸡肋
   * @param a 总数组
   * @param b 需要处理的桶
   * @param js 桶中有效数据量
   * @param divisor 被除数（决定比较数字第几位）
   * @param progress  回填数据的进度记录
   */
  private void doSort(int[] a, int[] b, int js, int divisor, Progress progress) {
    //如果桶中数据量小于50.就对桶中数据进行快速排序，然后装回a，如果不这样处理，效率将因为过多的桶而降低3倍以上
    if(js < 50) {
      KuaiSu.doSort(b, 0, js-1);
      for(int k = 0; k < js; k++)
        a[progress.now++] = b[k];
      return;
    }
    int[][] aa = new int[10][js];
    int[] jishu = new int[10];
    //装桶
    for(int i = 0; i < js; i++) {
      int index = b[i]/divisor%10;
      aa[index][jishu[index]++] = b[i];
    }
    //到了比较个位数的阶段，就直接把值全部填回原数组，在此阶段，前边的位数都是相等的
    if(divisor > 1) {
      divisor/=10;
      for(int i = 0; i < aa.length; i++) {
        if(jishu[i] > 0)
          doSort(a, aa[i], jishu[i], divisor, progress);
      }
    }else{
      for(int j = 0; j < aa.length; j++) {
        for(int k = 0; k < jishu[j]; k++) {
          a[progress.now++] = aa[j][k];
        }
      }
    }
  }

  /**
   * 该方法是从低到高根据每位数字创建桶并将a中数据全部装桶，然后按桶顺序再放回数据，
   * 放回过程中不需要关注桶内数据的具体顺序
   * 这样重复到最高位完成，数据自然就完成了排序
   *
   * 这种排序思想  多关键字排序，先排低级别的再高
   * @param a
   */
  void doSort2(int[] a) {
    for(int divisor = 1; divisor <= Constants.MAX_DATA_VALUE; divisor*=10) {
      int[][] aa = new int[10][a.length];
      int[] jishu = new int[10];
      for(int at : a)
        aa[at/divisor%10][jishu[at/divisor%10]++] = at;
      int progress = 0;
      for(int j = 0; j < aa.length; j++)
        for(int k = 0; k < jishu[j]; k++)
          a[progress++] = aa[j][k];
    }
  }

  public static void main(String[] args) {
    new JiShu2().testAll();
  }
}
